package com.googlecode.gaal.data.impl;

import java.util.BitSet;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.googlecode.gaal.data.api.IntervalSet;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree;
import com.googlecode.gaal.suffix.api.BinaryIntervalTree.BinaryNode;

/**
 * An implementation of the IntervalSet based on BitSet
 * 
 * @author akislev
 */
public class IntervalBitSet<E extends BinaryNode<E>> implements IntervalSet<E> {
    private final BinaryIntervalTree<E> tree;
    private final BitSet bitSet;

    public IntervalBitSet(BinaryIntervalTree<E> tree) {
        this.tree = tree;
        this.bitSet = new BitSet();
    }

    @Override
    public boolean add(E interval) {
        int middle = interval.middle();
        if (!bitSet.get(middle)) {
            bitSet.set(middle);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean remove(E interval) {
        int middle = interval.middle();
        if (bitSet.get(middle)) {
            bitSet.clear(middle);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean contains(E interval) {
        return !interval.isTerminal() && bitSet.get(interval.middle());
    }

    @Override
    public void intersect(IntervalSet<E> set) {
        IntervalBitSet<E> other = (IntervalBitSet<E>) set;
        if (tree != other.tree)
            throw new UnsupportedOperationException("can't intersect interval sets from different interval trees");
        bitSet.and(other.bitSet);
    }

    @Override
    public void union(IntervalSet<E> set) {
        IntervalBitSet<E> other = (IntervalBitSet<E>) set;
        if (tree != other.tree)
            throw new UnsupportedOperationException("can't union interval sets from different interval trees");
        bitSet.or(other.bitSet);
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private Iterator<E> iterator = tree.preorderIterator();
            private E next = advance();

            @Override
            public boolean hasNext() {
                return next != null;
            }

            @Override
            public E next() {
                if (next == null)
                    throw new NoSuchElementException();
                E interval = next;
                next = advance();
                return interval;
            }

            @Override
            public void remove() {
                iterator.remove();
            }

            private E advance() {
                while (iterator.hasNext()) {
                    E interval = iterator.next();
                    if (contains(interval)) {
                        return interval;
                    }
                }
                return null;
            }
        };
    }
}
